COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00006 00003		Notes for and about meeting jan 28.
C00009 00004
C00014 00005		The effects of an action or event are typically described
C00018 00006
C00020 00007	The Frame Problem as a Philosophical Problem
C00024 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.cb THE FRAME PROBLEM IN THE 1980s


	The McCarthy-Hayes frame problem is that of expressing in
some formal system common sense knowledge of what remains constant
when changes occur.  This information must be expressed in
a feasible and plausible way.  In particular, it is neither feasible
nor plausible to suppose that every expression of the consequences
of an event lists everything that doesn't change when the event
occurs.  We will discuss the somewhat more general
problem of giving epistemologically adequate expressions of knowledge
of the consequences of actions.

	Suppose a goal is to be achieved by a sequence of actions.  Each
action has preconditions for achieving
its intended effect, and we need assurance that each action results
in a situation that satisfies the preconditions for the next.

	One aspect of this is the simple frame problem.  If a plan
is to move block ⊗A onto block ⊗B and then move block ⊗C onto
block ⊗D, we must be assured that moving block ⊗A doesn't move
⊗C to a place from which it can't be moved and that moving ⊗C
doesn't destroy the effect of having moved ⊗A first.

	In describing action rules, we prefer a level of detail at which
actions have definite effects.  In general, goals are given at a lesser
level of detail than is required for determining the effects of actions.
Therefore, we need to distinguish between "states of affairs", which are
at that level of detail, and propositional fluents which may be at a
lesser level of detail.

	More generally yet, our knowledge of the effects of actions may be
at a lower level of detail than is required to determine the preconditions
for the desired subsequent actions.  This forces plans to contain servos,
i.e. %3while%1 loops, and conditional branches.  Example: if we have many
heavy boxes to move, our plan envisages resting whenever the moves have
made us tired, but our knowledge of the effects of moving boxes is
insufficient to determine when we will be tired.  Thus using incomplete
states of affairs is mitigated by including servos in the plans.

	Notes for and about meeting jan 28.

1. Why should philosophers be interested in the frame problem.  Dan
says yes, and John H. still has questions.

2. The frame problem may be the left ear of the elephant.  The elephant
may be the qualification problem.  Pat Hayes thinks the frame problem is
separate and easier, but this is perhaps because he thinks histories
solve the problem.  He had some worthwhile ways of expressing things, but
they all seemed translatable to the situation formalism.

3. The frame axioms discussed were

	%2∀xyzws.[z ≠ x ⊃ [on(z,w,result(move(x,y),s)) ≡ on(z,w,s)]]%1

	%2∀u x y s.[color(u,result(move(x,y),s)) = color(u,s)]%1

and the state vector form

	%2∀var1 var2 val state.[value(var2,assign(var1,val,state)) =
qif var1 = var2 qthen val qelse value(var2,state)]%1.

This needs to be decorated with a better explanation of its relation
to frames as objects.

4. STRIPS - nothing changes except what is said to change.

vs.

circumscription - nothing changes except what can bbe shown to change.

5. Models vs. common sense information.  Models have to be surrounded
by common sense information so that the robot will not be dumfounded
when some of the circumscriptions involved in their creation have
to be retracted.

6. The fact that what we know about the effects of an action is
often insufficient to assure the prerequisites of the next action
is mitigated by the use of servomechanisms.  The logical servo of
the Huberman chess program was mentioned.

7. Variable detail indices were expounded but not well enough to
get much response.

8. Peter Cheeseman (from Australia?) and Lew Creary took part.

9. The relation to philosophy question was interrupted many times,
but eventually began to fly.
Continuation Friday at 2:30.

Mathematical models

	In science, it is customary to use "mathematical models" of
the phenomena being studied.  Our view is that common sense knowledge
of a phenomenon cannot usually be formulated in terms of a mathematical
model of the kind used, because the common sense knowledge does not
provide enough information.  Finding a mathematical model is an
intellectual achievement not always possible.  When it is possible,
it requires disregarding some of the common sense information, so that
deciding when and how to apply the model requires the use of common
sense information that we have not succeeded in including in the model.

	We shall elaborate this point.  Consider a mathematical model
of a dynamic phenomenon.  Specifying the model requires defining a
state space and giving its laws of motion.  Specifying the state
space requires confining our attention to to certain aspects of the
world.  If other aspects of the world can affect how the aspects
of our concern change, this can only be known by common sense
reasoning outside the model.  To take an extreme example, our
model of the gravitational interactions of the solar system allows
predictions for hundreds of thousands of years and could be embodied
in a computer program that would give the jposition of aplanet over
such periods of time.  However, everyone knows that a hitherto
unobserved planet sized body might enter the solar system from the
outside and obviate the computations, and the model also doesn't
take into account the possibility that humanity might acquire the
ability and motivation to alter the course of the planets   The
information we possess about what humanity might do cannot be
integrated into the model, certainly not just by considering
the Newtonian and Einsteinian laws of gravity.

	When we come to biological phenomena, the situation is
worse.  Since the 1920s there have been elegant predator-prey
differential equation models, but they don't take into account
emigration from good areas for a species to areas whose
population depends on occasional immigration.

	When we come to common sense physics, the situation is
yet worse.
The basic problem is that what we know about the consequences of
an event is usually insufficient to say what event will occur
next.  Our knowledge of the possibilities does not take the
form of an assignment of probabilities to events in a definite
sample space.  The formation of a probabilistic model also requires
simplifying assumptions that force the model to be surrounded by
common sense information.
	The effects of an action or event are typically described
in English by saying what aspects of the world the event (we shall
include actions under events) changes, and how it changes them.
If we want a sufficient description of the situation that results
from an event so that we can determine the effects of future actions,
we need to know what doesn't change, and this is most things.
However, this is usually not described in English (it is somehow
implicit in the conversational situation), so that formalizing it
requires identifying the common sense presumptions about what doesn't
change.
This is called the frame problem, because in (McCarthy and Hayes 1970),
it was supposed that the independent aspects of the world were might
be regarded as attached to a "frame of reference" like the co-ordinate
systems used in physics.
One rather naive "solution" to the frame problem is to postulate that
everything not explicitly described as changing remains unchanged.
This idea is embodied in SRI's STRIPS formalism.
Its use requires that language be used in restricted way, and the
STRIPS programs obey such restrictions.
For example, if we describe blocks on a table using the predicate
on(x,y) specifying that block x is on block y in a situation implicitly
specified,
then we can describe actions as effecting the truth or falsity of
various on(x,y) statements.  However, this convention prevents us
from introducing a derived predicate above(x,y), since above(x,y)
statements are changed by changing on(x,y) statements.
This can be repaired by regarding certain of the predicates like on(x,y)
as primary and others like above(x,y) as secondary.
However, when we look at larger domains of common sense knowledge,
it doesn't seem that we have a clear notion of what is primary and
what is secondary.
For example, suppose we say that Pat went from Palo Alto to Boston.
Did his wife or car or clothes go with him?
The answer depends on whether the "going" is to be interpreted as
a permanent move or just a trip.

⊗on(x,y) is a quasi-proposition.  It can only have a truth value in a
context.
There is a predicate ⊗holds so that %2holds(on(x,y),qt)%1 is the assertion
that ⊗on(x,y) holds in the context qt.
Quasi-propositions are combined by quasi-boolean operators ⊗and, ⊗or and
⊗not.  We do not require that one of %2holds(p,qt)%1 or
%2holds(not_p,qt)%1 be true, because the context qt may not be
sufficiently detailed to determine a truth value for ⊗p.
We will have

	%2holds(p and q,qt) ≡ holds(p,qt) ∧ holds(q,qt)%1

and

	%2¬(holds(p,qt) ∧ holds(not p,qt))%1.

We may or may not postulate

	%2holds(p or q,qt) ≡ holds(p,qt) ∨ holds(q,qt)%1.

Contexts may be ordered, whereby qt ≤ qt' means that context
qt' has more information than context qt, leading to

	%2qt ≤ qt' ∧ holds(p,qt) ⊃ holds(p,qt').

The idea is that however detailed a context may be, there will be
quasi-propositions that require yet more details to decide.  There
might be a similar dual relation among quasi-propositions, satisfying

	%2p ≤ p' ∧ holds(p',qt) ⊃ holds(p,qt)%1.
The Frame Problem as a Philosophical Problem

	It is not obvious that the frame problem fits into
the previously recognized classes of problems.

	Consider the consequences of spilling a cup of coffee.
Let us suppose that these consequences are covered sufficiently
accurately by the known laws of mechanics and hydrodynamics.
Suppose this has been verified by experiments using accurately
measured cups with accurately measured  amounts of copy whose
viscosity, density, etc. have been accurately measured, and
we are interested in its being spilled on surfaces whose
properties have been measured.  Anyway assume that the results
of experiments correspond to thsse predicted by theory.

	Next suppose a cup of coffee is to be spilled under conditions
that permit no measurements, and people react to the event.  Also
consider a report of such an event.  Indeed consider a hypothetical
wire service news story beginning %2"Coffee spill kills three.  Three
fellows of the Center for Advanced Study in Behavioral Sciences
in Stanford, California were scalded to death when one of them
inadvertently knocked over a cup of coffee"%1.
Common sense physics tells us that this not possible.

	The facts that we use are not part of psychology, because
they deal with the physical world and would be the same if the
reasoner were a robot.  They are not part of physics as presently
conceived which is entirely satisfied if the laws of hydrodynamics
are adequate to predict the phenomenon given accurate measurements.
Some may regard them as too specialized for philosophy.  What is
probably not too specialized is the study of how it is possible to
represent the knowledge that permits common sense answers to the
questions?

Queries:

	Is McCarthy's distinction between collections of facts
and models obtained from circumscribing these facts needed?
(Incidentally, I fear a collision between this use of "model"
and that of "model theory".  Up to now these two subjects have
been too far apart for the conflict to matter, but this may
not continue).

	Do we need indices capable of indefinite refinement?

	Is the frame problem best treated as a case of the qualification
problem?  A good static qualification problem would help in comparing.